Leetcode 124.二叉树中的最大路径和

题目描述：

路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。

路径和 是路径中各节点值的总和。

给你一个二叉树的根节点 root ，返回其 最大路径和 。

示例 1：

1
2
3

输入：root = [1,2,3]
输出：6
解释：最优路径是 2 -> 1 -> 3 ，路径和为 2 + 1 + 3 = 6

示例 2：

1
2
3

输入：root = [-10,9,20,null,null,15,7]
输出：42
解释：最优路径是 15 -> 20 -> 7 ，路径和为 15 + 20 + 7 = 42

提示：

• 树中节点数目范围是 $[1, 3*10^4]$
• $-1000 <= Node.val <= 1000$

链接：

https://leetcode-cn.com/problems/binary-tree-maximum-path-sum

题目分析

  由于同一个节点在一条路径序列中至多出现一次，则某条路径中有且只有一个根结点，既可以是根结点作为路径端点，也可以是根结点连接来自左右子树的两个子路径。我们可以这样考虑，当一个结点作为根结点时，最大路径和即为左右子树中的最大子路径和（不超过 0 可以不要）加上结点本身的值。这样的话这个定义是递归的，结果应该可以通过递归遍历所有结点得到。
  但是存在着一个问题，我们需要计算的结果是一个结点连接左右子序列形成的序列和，而我们递归需要调用的子序列只能是以根结点作为端点的序列。如示例2，以结点 20 作为根结点的最大序列和是 [15, 20, 7]，但是当我们计算结点 -10 时，来自右子树 20 的子序列只能是 [20, 15] 或者是 [20, 7]。如果解决这个不同呢？由于我们要求的只是所有序列和中最大的那个，则我们可以使用一个全局变量存储最大序列和，而递归函数的返回值则是以这个结点为端点的最大序列和，以提供给上层函数使用。
  需要注意的是，结点值可以为负数，且必须至少选择一个结点，则有可能最终的最大路径和是负数，因此 result 的初始值需置为 INT_MIN 而不是 0。另外一个注意的点上面也已经提到，我们不一定要连接左右子序列，如果最大的左右子序列是负数的话，我们可以选择不连接。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution {
    int result = INT_MIN;

    int pathSum(TreeNode* root){
        if(!root) return 0;
        int left = pathSum(root->left);
        int right = pathSum(root->right);
        result = max(result, max(left, 0) + max(right, 0) + root->val);
        return max(0, max(left, right)) + root->val;
    }
public:
    int maxPathSum(TreeNode* root) {
        pathSum(root);
        return result;
    }
};

  时间复杂度：$O(n)$，其中 $n$ 为二叉树的结点数。我们对二叉树进行了一次遍历。
  空间复杂度：$O(n)$，其中 $n$ 为二叉树的结点数。递归的最大深度为 $n$。

官方题解

  与我的代码有一点小小的不同（PS：第一次困难题（PPS：这题其实有点简单不像是困难题）自己有思路，在完全没看官方题解的前提下居然写出了几乎一样的代码，连全局变量的使用也一样，有点神奇），官方题解在计算 left 和 right 的值时就已经与 0 进行比较，下面更新 result 和函数返回值的时候就无需进行比较。在我的代码里，left 和 right 表示最大子序列和，可以为负数；在官方题解里，它们表示的含义变成了子树的 “贡献度”，如果子序列和为负数则不进行连接，贡献度为 0。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

class Solution {
private:
    int maxSum = INT_MIN;

public:
    int maxGain(TreeNode* node) {
        if (node == nullptr) {
            return 0;
        }
        
        // 递归计算左右子节点的最大贡献值
        // 只有在最大贡献值大于 0 时，才会选取对应子节点
        int leftGain = max(maxGain(node->left), 0);
        int rightGain = max(maxGain(node->right), 0);

        // 节点的最大路径和取决于该节点的值与该节点的左右子节点的最大贡献值
        int priceNewpath = node->val + leftGain + rightGain;

        // 更新答案
        maxSum = max(maxSum, priceNewpath);

        // 返回节点的最大贡献值
        return node->val + max(leftGain, rightGain);
    }

    int maxPathSum(TreeNode* root) {
        maxGain(root);
        return maxSum;
    }
};